Modern processors typically use branch predictors that predict the direction that a branch will take and the target address of the branch. A given branch instruction does not always go in the same direction for each execution of the instruction. Also, even when the direction is known, the target of a branch, e.g. an indirect branch, may change from one execution to another. Thus, it is customary to use some information about the path leading to the branch to make a more informed prediction of the direction and target of a branch.
Such information about the path leading to an instruction is also useful in other contexts. One example is in dynamic code optimization, where the nature of optimization can often be improved from the knowledge of the path taken to the block that needs to be optimized. Another example is in the prediction of “last-touch” of a shared object, where the path taken to an access of the object can often determine whether that object will be accessed again by the same processor or by a different processor.
A trivial way of identifying an instruction execution path is by identifying the addresses of all instructions and concatenating them together in the order of execution. However, such a representation is prohibitively long for a reasonable-sized sequence of instructions.
The instruction path can also be represented by a sequence of tuples, each tuple comprising the address of a basic block and the length of the basic block. This information is sufficient because, by definition, all instructions in a basic block must be executed in sequence once the basic block is entered. However this representation has a lot of redundant information because the address of a branch target can often be deciphered, especially in modern ISAs like the PowerPC ISA, from the bits in the branch instruction itself.
In a sequence of instructions that consists only of PC-relative branches where the starting address of the sequence is known, it is sufficient to simply record the direction taken by the branch, for example, a 1 for a taken branch, a 0 for a fall-through or not-taken branch. From the starting address, the path through the code can be completely determined by this sequence of 1's and 0's.
This sequence is not sufficient in the presence of indirect branches, where the address of the target of the branch is not available in the instruction itself; rather it is loaded into a register.
Thus there is a need for a mechanism to more accurately identify the path of instruction execution leading up to a branch or any other instruction whose behavior needs to be predicted and to do so using a compact representation.